package mpp;

import java.util.concurrent.atomic.AtomicMarkableReference;

public class LockFreeListQueue<T> implements PQueue<T> {
	volatile NodeEx4<T> head;
	
	public LockFreeListQueue() {
		super();
		head = new NodeEx4<T>(null, Integer.MIN_VALUE);
		head.next = new AtomicMarkableReference<NodeEx4<T>>(new NodeEx4<T>(null, Integer.MAX_VALUE), false);
	}

	@Override
	public void add(T item, int score) {
		while(true){
			Window<T> window = find(head, score);
			NodeEx4<T> pred = window.pred, curr = window.curr;
			
			if(curr.key == score) {
				return;
				
			}else{
				NodeEx4<T> node = new NodeEx4<T>(item, score);
				node.next = new AtomicMarkableReference<NodeEx4<T>>(curr,false);
				
				if(pred.next.compareAndSet(curr, node,false,false)) {
					return;
				}
			}
		}
		
	}
	
	@Override
	public T removeMin() {
		boolean snip;
		while(true){
			Window<T> window = findFirst(head);
			NodeEx4<T> pred = window.pred, curr = window.curr;
			
			// Incase there are no other nodes left.
			if(curr.key == Integer.MAX_VALUE) {
				return null;
			}else{
				NodeEx4<T> succ = curr.next.getReference();
				snip = curr.next.attemptMark(succ,true);
				if(!snip)
					continue;
				pred.next.compareAndSet(curr, succ,false,false);
				return curr.value;
			}
		}
		
	}

	
	private Window<T> find(NodeEx4<T> head,int key) {
		NodeEx4<T> pred =null, curr =null, succ =null;
		boolean[] marked = {false};
		boolean snip;
  retry:while(true){
			pred = head;
			curr = pred.next.getReference();
			while(true){
				succ = curr.next.get(marked);
				while(marked[0]) {
					snip = pred.next.compareAndSet(curr, succ,false,false);
					if(!snip) continue retry;
					curr = succ;
					succ = curr.next.get(marked);
					}
				if(curr.key >= key)
					return new Window<T>(pred, curr);
				 pred = curr;
				 curr = succ;
				}
			}	
	}
	
	private Window<T> findFirst(NodeEx4<T> head){
		NodeEx4<T> pred = null, curr = null, succ = null;
		boolean[] marked = { false };
		boolean snip;
		retry: while (true) {
			pred = head;
			curr = pred.next.getReference();
			while (true) {
				succ = curr.next.get(marked);
				while (marked[0]) {
					snip = pred.next.compareAndSet(curr, succ, false, false);
					if (!snip)
						continue retry;
					curr = succ;
					succ = curr.next.get(marked);
				}
				
				// Return the first not deleted node.
				return new Window<T>(pred, curr);
			}
		}
		
	}
	
	
}
